Add to array form of integer [Schoolbook Addition]

Time: O(N+LogK); Space: O(1); easy

For a non-negative integer X, the array-form of X is an array of its digits in left to right order. For example, if X = 1231, then the array form is [1, 2, 3, 1].

Given the array-form A of a non-negative integer X, return the array-form of the integer X + K.

Example 1:

Input: A = [1, 2, 0, 0], K = 34

Output: [1, 2, 3, 4]

Explanation:

  • 00 + 34 = 1234

Example 2:

Input: A = [2, 7, 4], K = 181

Output: [4, 5, 5]

Explanation:

  • 4 + 181 = 455

Example 3:

Input: A = [2, 1, 5], K = 806

Output: [1, 0, 2, 1]

Explanation:

  • 5 + 806 = 1021

Example 4:

Input: A = [9, 9, 9, 9, 9, 9, 9, 9, 9, 9], K = 1

Output: [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

Explanation:

  • 99999999 + 1 = 10000000000

Notes:

  • 1 <= len(A) <= 10000

  • 0 <= A[i] <= 9

  • 0 <= K <= 10000

  • If len(A) > 1, then A[0] != 0

1. Schoolbook Addition

Intuition Let’s add numbers in a schoolbook way, column by column. For example, to add 123 and 912, we add 3+2, then 2+1, then 1+9. Whenever our addition result is more than 10, we carry the 1 into the next column. The result is 1035.

Algorithm We can do a variant of the above idea that is easier to implement - we put the entire addend in the first column from the right.

Continuing the example of 123 + 912, we start with [1, 2, 3+912]. Then we perform the addition 3+912, leaving 915. The 5 stays as the digit, while we ‘carry’ 910 into the next column which becomes 91.

We repeat this process with [1, 2+91, 5]. We have 93, where 3 stays and 90 is carried over as 9. Again, we have [1+9, 3, 5] which transforms into [1, 0, 3, 5].

[5]:

class Solution1(object):
    """
    Time: O(max(N,LogK)) where N is the length of A.
    Space: O(max(N, LogK)).
    """
    def addToArrayForm(self, A, K):
        """
        :type A: List[int]
        :type K: int
        :rtype: List[int]
        """
        A[-1] += K
        for i in range(len(A) - 1, -1, -1):
            carry, A[i] = divmod(A[i], 10)
            if i:
                A[i-1] += carry
        if carry:
            A = list(map(int, str(carry))) + A
        return A

[6]:

s = Solution1()
A = [1, 2, 0, 0]
K = 34
assert s.addToArrayForm(A, K) == [1, 2, 3, 4]
A = [2, 7, 4]
K = 181
assert s.addToArrayForm(A, K) == [4, 5, 5]
A = [2, 1, 5]
K = 806
assert s.addToArrayForm(A, K) == [1, 0, 2, 1]
A = [9, 9, 9, 9, 9, 9, 9, 9, 9, 9]
K = 1
assert s.addToArrayForm(A, K) == [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

[9]:

class Solution2(object):
    """
    Time: O(N+LogK)
    Space: O(1)
    """
    def addToArrayForm(self, A, K):
        """
        :type A: List[int]
        :type K: int
        :rtype: List[int]
        """
        A.reverse()
        carry, i = K, 0
        A[i] += carry
        carry, A[i] = divmod(A[i], 10)
        while carry:
            i += 1
            if i < len(A):
                A[i] += carry
            else:
                A.append(carry)
            carry, A[i] = divmod(A[i], 10)
        A.reverse()
        return A

[10]:

s = Solution2()
A = [1, 2, 0, 0]
K = 34
assert s.addToArrayForm(A, K) == [1, 2, 3, 4]
A = [2, 7, 4]
K = 181
assert s.addToArrayForm(A, K) == [4, 5, 5]
A = [2, 1, 5]
K = 806
assert s.addToArrayForm(A, K) == [1, 0, 2, 1]
A = [9, 9, 9, 9, 9, 9, 9, 9, 9, 9]
K = 1
assert s.addToArrayForm(A, K) == [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]